package leetcodev1.树;

import leetcodev1.链表.Solution;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class LeetCode102 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }

        TreeNode virtualNode = new TreeNode(-1);//占位计数用 全是virtualNode则停止
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        int count = 1, level = 0, virtualCount = 1;
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            TreeNode left = node.left != null ? node.left : virtualNode;
            TreeNode right = node.right != null ? node.right : virtualNode;
            queue.add(left);
            queue.add(right);
            count--;

            if (node != virtualNode) {
                tmp.add(node.val);
            } else {
                virtualCount--;
            }

            if (virtualCount == 0) {
                break;
            }

            //当前层迭代完成
            if (count == 0) {
                level++;
                count = level * 2;
                virtualCount = count;
                ret.add(tmp);
                tmp = new ArrayList<>();
            }
        }

        return ret;
    }
}

class Answer102 {
    //广度优先遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) {
            return ret;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();//每次获取当前队列长度
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }

        return ret;
    }

}
